package calculation;

public class Calcu {
    public static void main(String[] args) {
        Trie trie = new Trie();

        trie.insert("hello");
        trie.insert("hell");
        trie.insert("hel");
        trie.insert("he");
        trie.insert("h");

        System.err.println(trie.search("a"));
    }

    public static String longgestWord(TrieNode root) {
        return "";
    }

}

// 字典树又称为前缀树或者Trie树，是处理字符串的一种数据结构
// 字典树一般具有以下功能
// - insert(String word);  // 添加word，可重复
// - delete(String word);  // 删除word，如果有多个相同的word，只删除一个
// - search(String word);  // 查询word是否在字典树中
// - prefixNumber(String prefix);  // 返回以prefix为前缀的单词数量

// 字典树的一些特征
// - 根节点没有字符路径

class Trie {

    TrieNode root;

    Trie() {
        root = new TrieNode();
    }

    void insert(String word) {
        if (word == null) return;

        TrieNode node = root;
        node.path ++;  // 以该节点为开头的单词个数

        char[] words = word.toCharArray();
        int index = 0;  // 字母应该放置的位置
        for (int i = 0; i < words.length; i++) {
            index = words[i] - 'a';  // 当前字母应该放置的位置
            if (node.children[index] == null) {
                node.children[index] = new TrieNode();
            }
            node = node.children[index];
            node.path ++;  // 当前节点被使用了一次
        }
        node.end ++;  // 当前节点为end尾结点
    }

    boolean search(String word) {
        if (word == null) return false;
        TrieNode node = root;
        char[] words = word.toCharArray();
        int index = 0;
        for (int i = 0; i < words.length; i++) {
            index = words[i] - 'a';  // 当前字母放置的位置
            if (node.children[index] == null) return false;  // 当前位置上没有字母
            node = node.children[index];
        }
        return node.end > 0;  // 当前节点是否有单词将其为终止节点
    }

    void delete(String word) {
        if (search(word)) {  // 当前字母存在
            char[] words = word.toCharArray();
            TrieNode node = root;
            node.path --;
            int index = 0;
            for (int i = 0; i < words.length; i++) {
                index = words[i] - 'a';
                node.children[index].path --;  // 当前节点使用次数减一
                if (node.children[index].path == 0) {  // 到达了根节点
                    node.children[index] = null;
                    return;
                }
                node = node.children[index];
            }
            node.end --;
        }
    }

    int prefixNumber(String prefix) {
        if (prefix == null) return 0;
        TrieNode node = root;
        char[] words = prefix.toCharArray();
        int index = 0;
        for (int i = 0; i < words.length; i++) {
            index = words[i] - 'a';
            if (node.children[index] == null) return 0;
            node = node.children[index];
        }
        return node.path;
    }
}

class TrieNode {
    int path;  // 多少单词公用这一个节点
    int end;   // 多少单词以这个节点结尾
    TrieNode[] children;

    TrieNode() {
        path = 0;
        end = 0;
        children = new TrieNode[26];  // 26个英文字母
    }
}